﻿#ifndef XBINARYTREE_H
#define XBINARYTREE_H
#include"XMultiWayTree.hpp"
#include<iostream>
//二叉树
namespace XBTree
{
	enum childType { left, right };//孩子定义
	//二叉树遍历方式
	enum Traversing
	{
		Preorder,//前序(根左右)
		Inorder,//中序(左根右)
		Postorder//后序(左右根)
	};
}

//二叉树
template<typename Ty>
class XBinaryTree :protected XMultiWayTree<Ty>
{
public:
	
	XBinaryTree(XBinaryTree<Ty>* parent=NULL);
	XBinaryTree(const Ty& data, XBinaryTree<Ty>* parent = NULL);
	//设置父节点
	void setParent(XBinaryTree<Ty>* parent);
	//获取父节点指针
	 XBinaryTree<Ty>* parent()const;
	//获取左节点
	XBinaryTree<Ty>* leftChild()const;
	//设置左节点
	void setLeftChild(XBinaryTree<Ty>* node);
	//获取右节点
	XBinaryTree<Ty>* rightChild()const;
	//设置右节点
	void setRightChild(XBinaryTree<Ty>* node);
	//遍历二叉树
	std::vector<XBinaryTree<Ty>*>traversing(XBTree::Traversing T);
	//设置数据
	void setData(const Ty& data);
	//获取一个数据
	Ty data()const;
	//清空树只剩下自己(递归的方式清空自己的全部孩子)
	void clearTree()const;
public:
	//前序
	static std::vector<XBinaryTree<Ty>*>Traversing_Preorder(XBinaryTree<Ty>* root);
	//中序
	static std::vector<XBinaryTree<Ty>*>Traversing_Inorder(XBinaryTree<Ty>* root);
	//后续
	static std::vector<XBinaryTree<Ty>*>Traversing_Postorder(XBinaryTree<Ty>* root);
	//清空树包括自己
	static void clearTree(XBinaryTree<Ty>* root);
public:
	/*friend std::ostream& operator<<(std::ostream& out, XBinaryTree<Ty>* root);*/
protected:
	void init(XBinaryTree<Ty>* parent);
};
template<typename Ty>
inline std::ostream& operator<<(std::ostream& out, XBinaryTree<Ty>* root)
{
	out << root->data() << " ";
	return out;
}
template<typename Ty>
inline XBinaryTree<Ty>::XBinaryTree(XBinaryTree<Ty>* parent)
{
	init(parent);
}
template<typename Ty>
inline XBinaryTree<Ty>::XBinaryTree(const Ty& data, XBinaryTree<Ty>* parent)
{
	init(parent);
	setData(data);
}
template<typename Ty>
inline void XBinaryTree<Ty>::setParent(XBinaryTree<Ty>* parent)
{
	XMultiWayTree<Ty>::setParent(parent);
}
template<typename Ty>
inline  XBinaryTree<Ty>* XBinaryTree<Ty>::parent() const
{
	return (XBinaryTree<Ty>*)XMultiWayTree<Ty>::parent();
}
template<typename Ty>
inline XBinaryTree<Ty>* XBinaryTree<Ty>::leftChild()const
{
	if (XBTree::left >= XMultiWayTree<Ty>::m_ChildList.size())
		return nullptr;
	return (XBinaryTree<Ty>*)XMultiWayTree<Ty>::m_ChildList[XBTree::left];
}

template<typename Ty>
inline void XBinaryTree<Ty>::setLeftChild(XBinaryTree<Ty>* node)
{
	if (XBTree::left < XMultiWayTree<Ty>::m_ChildList.size())
	{
		XMultiWayTree<Ty>::m_ChildList[XBTree::left] = node;
		node->setParent(this);
	}
}
template<typename Ty>
inline XBinaryTree<Ty>* XBinaryTree<Ty>::rightChild()const
{
	if (XBTree::right >= XMultiWayTree<Ty>::m_ChildList.size())
		return nullptr;
	return (XBinaryTree<Ty>*)XMultiWayTree<Ty>::m_ChildList[XBTree::right];
}
template<typename Ty>
inline void XBinaryTree<Ty>::setRightChild(XBinaryTree<Ty>* node)
{
	if (XBTree::right < XMultiWayTree<Ty>::m_ChildList.size())
	{
		XMultiWayTree<Ty>::m_ChildList[XBTree::right] = node;
		node->setParent(this);
	}
}

template<typename Ty>
inline std::vector<XBinaryTree<Ty>*> XBinaryTree<Ty>::traversing(XBTree::Traversing T)
{
	switch (T)
	{
	case  XBTree::Preorder:
		return std::move(XBinaryTree<Ty>::Traversing_Preorder(this));
	case XBTree::Inorder:
		return std::move(XBinaryTree<Ty>::Traversing_Inorder(this));
	case XBTree::Postorder:
		return std::move(XBinaryTree<Ty>::Traversing_Postorder(this));
	default:
		return std::move(std::vector<XBinaryTree<Ty>*>());
	}
}

template<typename Ty>
inline void XBinaryTree<Ty>::setData(const Ty& data)
{
	XMultiWayTree<Ty>::setData(data, 0);
}
template<typename Ty>
inline Ty XBinaryTree<Ty>::data() const
{
	return XMultiWayTree<Ty>::data(0);
}
template<typename Ty>
inline void XBinaryTree<Ty>::clearTree() const
{
	XMultiWayTree<Ty>::clearTree();
}
template<typename Ty>
inline std::vector<XBinaryTree<Ty>*> XBinaryTree<Ty>::Traversing_Preorder(XBinaryTree<Ty>* root)
{
	std::vector<XBinaryTree<Ty>*> vector;
	std::stack<XBinaryTree<Ty>*> stack;
	stack.push(root);
	XBinaryTree<Ty>* currentNode = NULL;//当前节点指针
	while (!stack.empty())
	{
		currentNode = stack.top();
		stack.pop();
		XBinaryTree<Ty>* LChild = currentNode->leftChild();
		XBinaryTree<Ty>* RChild = currentNode->rightChild();
		if (RChild != NULL)
			stack.push(RChild);
		if (LChild != NULL)
			stack.push(LChild);
		vector.push_back(currentNode);
	}
	return std::move(vector);
}
template<typename Ty>
inline std::vector<XBinaryTree<Ty>*> XBinaryTree<Ty>::Traversing_Inorder(XBinaryTree<Ty>* root)
{
	std::vector<XBinaryTree<Ty>*> vector;
	std::stack<XBinaryTree<Ty>*> stack;
	XBinaryTree<Ty>* currentNode = root;//当前节点指针
	while (!stack.empty() || currentNode != NULL)
	{
		if (currentNode != NULL)
		{
			stack.push(currentNode);
			currentNode = currentNode->leftChild();
		}
		else
		{
			XBinaryTree<Ty>* XListNode = stack.top();
			vector.push_back(XListNode);
			currentNode = XListNode->rightChild();
			stack.pop();
		}
	}
	return std::move(vector);
}
template<typename Ty>
inline std::vector<XBinaryTree<Ty>*> XBinaryTree<Ty>::Traversing_Postorder(XBinaryTree<Ty>* root)
{
	std::vector<XBinaryTree<Ty>*> vector;
	std::stack<XBinaryTree<Ty>*> stack;
	stack.push(root);
	XBinaryTree<Ty>* currentNode = NULL;//当前节点指针
	while (!stack.empty())
	{
		currentNode = stack.top();
		stack.pop();
		vector.push_back(currentNode);
		XBinaryTree<Ty>* LChild = currentNode->leftChild();
		XBinaryTree<Ty>* RChild = currentNode->rightChild();
		if (LChild != NULL)
			stack.push(LChild);
		if (RChild != NULL)
			stack.push(RChild);
	}
	std::reverse(vector.begin(), vector.end());
	return std::move(vector);
}
template<typename Ty>
inline void XBinaryTree<Ty>::clearTree(XBinaryTree<Ty>* root)
{
	XMultiWayTree<Ty>::clearTree(root);
}
template<typename Ty>
inline void XBinaryTree<Ty>::init(XBinaryTree<Ty>*  parent)
{
	XMultiWayTree<Ty>::m_DataList.resize(1);
	XMultiWayTree<Ty>::m_ChildList.resize(2);
	XMultiWayTree<Ty>::m_parent=parent;
}
#endif // XBinaryTree_H


